package com.jonlandrum.collections.BinarySearchTree.SplayTree;

import com.jonlandrum.collections.BinarySearchTree.BinarySearchNode;
import com.jonlandrum.collections.BinarySearchTree.BinarySearchTree;
import com.jonlandrum.collections.BinarySearchTree.LinkedAdjustableTreeADT;
import com.jonlandrum.collections.BinarySearchTree.LinkedBinarySearchNode;

public class LinkedSplayTree<T extends Comparable<T>> extends LinkedAdjustableTreeADT<T> implements BinarySearchTree<T>, SplayTree<T> {
    /**
     * Constructs an empty LinkedSplayTree.
     */
    public LinkedSplayTree() {
        super();
    }

    /**
     * Constructs a new LinkedSplayTree with the given node set as the root element.
     *
     * @param node The node to set as this tree's root element
     */
    public LinkedSplayTree(BinarySearchNode<T> node) {
        super(node);
    }

    /**
     * Inserts a new data element into this tree.
     *
     * @param data The data element to insert into this tree
     */
    @Override
    public BinarySearchNode<T> insert(T data) {
        return this.insert(new LinkedBinarySearchNode<>(data));
    }

    /**
     * Inserts a new node into this tree.
     *
     * @param node The node to insert into this tree
     */
    @Override
    public BinarySearchNode<T> insert(BinarySearchNode<T> node) {
        node = super.insert(node);
        splay((LinkedBinarySearchNode<T>) node);
        return node;
    }

    /**
     * Deletes a data element from this tree.
     *
     * @param data The data element to be removed from this tree
     * @return The replacement of the data element removed from this tree
     */
    @Override
    public BinarySearchNode<T> delete(T data) {
        return this.delete(new LinkedBinarySearchNode<>(data));
    }

    /**
     * Deletes a node from this tree.
     *
     * @param node The node to be removed from this tree
     * @return The successor of the node removed from this tree
     */
    @Override
    public BinarySearchNode<T> delete(BinarySearchNode<T> node) {
        node = search(node);
        node = super.delete(node);
        return node;
    }

    /**
     * Searches for a specific data element in this tree.
     *
     * @param data The data element of the same value as the node searched for
     * @return The node searched for
     */
    @Override
    public BinarySearchNode<T> search(T data) {
        return this.search(new LinkedBinarySearchNode<>(data));
    }

    /**
     * Searches for a specific data element in this tree.
     *
     * @param node A node containing the same value as the node searched for
     * @return The node searched for
     */
    @Override
    public BinarySearchNode<T> search(BinarySearchNode<T> node) {
        node = super.search(node);
        splay((LinkedBinarySearchNode<T>) node);
        return node;
    }

    private void splay(LinkedBinarySearchNode<T> target) {
        if (target.hasData()) {
            while (target != getRoot()) {
                if (target.isLeft()) {
                    rotateRight(target.getParent());
                } else if (target.isRight()) {
                    rotateLeft(target.getParent());
                }
            }
        }
    }
}
